package main

import "sort"

//三个元素和为0
// 排序后固定一个数nums[i]
// 1. 固定一个数nums[i]若是>0 那么和必然不等于0 跳过
// 2. 若是nums[i] == nums[i+1], 则去重, 跳过。防止出现这种情况[[1,0,-1][1,0,-1][1,0,-1]]
// 3. 若是nums[i] < 0,则向后生成两个指针left和right
// 4. 若是nums[left] == nums[left+1] 则left++
// 5. 若是nums[right] == nums[right-1] 则right--

func threeSum(nums []int) [][]int{
	ans :=make([][]int,0)
	if nums == nil ||len(nums) <3{
		return ans
	}
	sort.Ints(nums)
	//此曾for循环nums[i]的定位一直循环到nums[i]==0
	for i:=0;i<len(nums);i++{
		if nums[i]>0{
			break
		}
		if i>0 && nums[i] == nums[i-1]{
			continue
		}
        left :=i+1
        right :=len(nums)-1
        for left <right{
        	sum :=nums[i]+nums[left]+nums[right]
        	if sum == 0{
        		res :=[]int{nums[i],nums[left],nums[right]}
        		ans =append(ans,res)
        		//需要left<right 写在 && 的左边，先行判断，因为&&有短裤求值的特性f
        		for left <right && nums[left] == nums[left+1]{
        			left++
				}
				for left<right && nums[right] == nums[right-1]{
					right--
				}
				left++
				right--
			}else if sum >0{
				right--
			}else if sum <0{
				left++
			}
		}
	}
return ans
}

//四数之和
func fourSum(nums []int,target int)(ss [][]int){
	sort.Ints(nums)
	n:=len(nums)
	for i:=0;i<n-3 && nums[i] +nums[i+1] +nums[i+2] +nums[i+3]<=target;i++{
		if i>0 && nums[i] == nums[i-1] || nums[i] +nums[n-3]+nums[n-2]+nums[n-1]<target{
			continue
		}
		for j:=i+1;j<n-2&&nums[i]+nums[j]+nums[j+1]+nums[j+2] <=target;j++{
			if j>i+1 && nums[j] ==nums[j-1] || nums[i]+nums[j]+nums[n-2]+nums[n-1]<target{
				continue
			}
			for left,right :=j+1,n-1;left <right;{
				if sum :=nums[i]+nums[j]+nums[left];sum ==target{
					ss =append(ss,[]int{nums[i],nums[j],nums[left],nums[right]})
					for left++;left<right && nums[left] ==nums[left-1];{
						left++
					}
					for right--;left<right&& nums[right] ==nums[right+1];{
						right--
					}
				}else if sum<target{
					left++
				}else{
					right--
				}
			}
		}
	}
	return
}
